Partitioned multiprocessor scheduling has been widely accepted in academiaand industry to statically assign and partition real-time tasks onto identicalmultiprocessor systems. This paper studies fixed-priority partitionedmultiprocessor scheduling for sporadic real-time systems, in whichdeadline-monotonic scheduling is applied on each processor. Prior to thispaper, the best known results are by Fisher, Baruah, and Baker with speedupfactors $4-\frac{2}{M}$ and $3-\frac{1}{M}$ for arbitrary-deadline andconstrained-deadline sporadic real-time task systems, respectively, where $M$is the number of processors. We show that a greedy mapping strategy has aspeedup factor $3-\frac{1}{M}$ when considering task systems with arbitrarydeadlines. Such a factor holds for polynomial-time schedulability tests andexponential-time (exact) schedulability tests. Moreover, we also improve thespeedup factor to $2.84306$ when considering constrained-deadline task systems.We also provide tight examples when the fitting strategy in the mapping stageis arbitrary and $M$ is sufficiently large. For both constrained- andarbitrary-deadline task systems, the analytical result surprisingly shows thatusing exact tests does not gain theoretical benefits (with respect to speedupfactors) for an arbitrary fitting strategy.
展开▼
